package com.leetcode;

/**
 * 2874. 有序三元组中的最大值 II
 * 给你一个下标从 0 开始的整数数组 nums 。
 * <p>
 * 请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
 * <p>
 * 下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。
 */
public class LeetCode2874 {
  
  public static void main(String[] arg0) {
    int[] nums = {12, 6, 1, 2, 7};
    
    if (nums.length < 3) {
      System.out.println("数量不足");
      return;
    }
    
    long result = Long.MIN_VALUE;
    
    // nums[k] 的值其实是随着j的值而固定的，可以用一个数字记录下来
    int[] maxKs = new int[nums.length - 2];
    for (int i = nums.length - 1; i > 1; i--) {
      if (i == nums.length - 1) {
        maxKs[i - 2] = nums[i];
      } else {
        maxKs[i - 2] = Math.max(maxKs[i - 1], nums[i]);
      }
    }

    // nums[i] - nums[j] 的值也是随着j的值固定的，找出 nums[i] 的最大值，nums[i] - nums[j] 就最大
    long maxX = Long.MIN_VALUE;
    for (int i = 1; i < nums.length - 1; i++) {
      maxX = Math.max(maxX, nums[i - 1]);
      long currentResult = (maxX - nums[i]) * maxKs[i - 1];
      result = Math.max(result, currentResult);
    }
    
    System.out.println("result: " + (result < 0 ? 0 : result));
    
  }
}